#include<iostream>
#include<vector>
using namespace std;
/*
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
解题思路：
本题与打家劫舍1相类似，分为三种情况，考虑首元素，则不考虑尾元素，考虑尾元素则不考虑首元素
首尾元素都不考虑，但是第三中情况是被前两种情况包含进去，所以将打家劫舍1的情况分为是否考虑首尾元素，然后取最大值
*/
int dp(vector<int> nums)
{
    //创建dp数组
    vector<int> dp(nums.size());
    //初始化dp数组
    if(nums.size()<2)
        return nums[0];
    if(nums.size()<3)
        return max(nums[0],nums[1]);
    dp[0] =  nums[0];
    dp[1] = max(nums[0],nums[1]);
    //考虑首元素不考虑尾元素
    for(int i=2;i<nums.size()-1;i++)
        dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
    int max1 = dp[nums.size()-2];
    //不考虑首元素
    dp[1] = nums[1];
    dp[2] = max(nums[1],nums[2]);
    for(int i=3;i<nums.size();i++)
        dp[i] = max(nums[i]+dp[i-2],dp[i-1]);
    return max(max1,dp[nums.size()-1]);
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums);
    return 0;
}